//有 N 个网络节点，标记为 1 到 N。 
//
// 给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从
//源节点传递到目标节点的时间。 
//
// 现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。 
//
// 
//
// 示例： 
//
// 
//
// 输入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
//输出：2
// 
//
// 
//
// 注意: 
//
// 
// N 的范围在 [1, 100] 之间。 
// K 的范围在 [1, N] 之间。 
// times 的长度在 [1, 6000] 之间。 
// 所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。 
// 
// Related Topics 堆 深度优先搜索 广度优先搜索 图 
// 👍 210 👎 0

package com.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//Java：网络延迟时间
class P743NetworkDelayTime {
    public static void main(String[] args) {
        Solution solution = new P743NetworkDelayTime().new Solution();
        // TO TEST
        int[][] times = {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
        System.out.println(solution.networkDelayTime(times, 4, 2));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int networkDelayTime(int[][] times, int N, int K) {
            //邻接表
            List<List<int[]>> adj = new ArrayList<>(N + 1);
            for (int i = 0; i <= N; i++) {
                adj.add(new ArrayList<>());
            }
            for (int i = 0; i < times.length; i++) {
                adj.get(times[i][0]).add(new int[]{times[i][1], times[i][2]});
            }
            boolean[] visited = new boolean[N + 1];
            int[] dist = new int[N + 1];
            //初始值设置为MAX_VALUE
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[K] = 0;
            while (true) {
                int canNode = -1;
                int canDist = Integer.MAX_VALUE;
                //寻找剩下所有节点中，距离源节点路径最近的，加入dist
                for (int i = 1; i <= N; i++) {
                    if (!visited[i] && dist[i] < canDist) {
                        canNode = i;
                        canDist = dist[i];
                    }
                }
                if (canNode < 0) {
                    //所有节点都已经加入了dist,跳出循环
                    break;
                }
                visited[canNode] = true;
                //找到
                for (int i = 0; i < adj.get(canNode).size(); i++) {
                    int[] ints = adj.get(canNode).get(i);
                    dist[ints[0]] = Math.min(dist[ints[0]], dist[canNode] + ints[1]);
                }

            }
            int ans = 0;
            for (int i = 1; i <= N; i++) {
                if (dist[i] == Integer.MAX_VALUE) {
                    return -1;
                }
                ans = Math.max(ans, dist[i]);
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}